1881F - Minimum Maximum Distance - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define ll long long
#define vll vector<long long>
#define all(x) x.begin(),x.end()
#define ld long double
const int N = 200008;

ll poww(ll a,ll b,ll mod){
    ll res=1;if(b<0||b>=mod)b=(b%(mod-1)+mod-1)%(mod-1);
    for(;b;b>>=1,a=1ll*a*a%mod)
      if(b&1)res=1ll*res*a%mod;
    return res;
}

int n,k;
vector<int> v[N];
int dis[N];
bool fromTree[N],marked[N];

int dfs(int x,int p)
{
    if(marked[x])fromTree[x]=true;
//    par[x]=p;
    for(int z:v[x]){
        if(z!=p){
            dfs(z,x);
            fromTree[x] |= fromTree[z];
        }
    }
}

int mover(int x,int p)
{

    for(int z:v[x]){
        if(p!=z && fromTree[z]){
            dis[z]=dis[x]+1;
            mover(z,x);
        }
    }
}

int sol(int x,int p,int maxi)
{
    if(dis[x]==(maxi+1)/2){
        return x;
    }

    int ans =0 ;
    for(int z:v[x]){
        if(z!=p && fromTree[z]){
            ans = max(ans,sol(z,x,maxi));
        }
    }

    return ans;
}

void solve()
{
    cin>>n>>k;
    for(int i=0;i<=n;i++){
        fromTree[i]=marked[i]=false;
        dis[i]=0;
        v[i].clear();
    }

    for(int i=0;i<k;i++){
        int x;cin>>x;
        marked[x]=1;
    }

    for(int i=0;i<n-1;i++){
        int x,y;cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }

    int node1 = 0;
    for(int i=1;i<=n;i++){
        if(marked[i]){
            dfs(i,0);
            mover(i,0);
            node1=i;
            for(int j=1;j<=n;j++){
                if(dis[j]>dis[node1] && fromTree[j])node1=j;
            }
            break;
        }
    }

    for(int i=0;i<=n;i++)dis[i]=0;
    mover(node1,0);

    int node2=node1;
    for(int i=1;i<=n;i++){
        if(fromTree[i] && dis[i]>dis[node2]){
            node2=i;
        }
    }

    cout<<dis[sol(node1,0,dis[node2])]<<endl;

}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t=1;
    cin>>t;
while(t--)solve();


    return 0;
}